This invention relates generally to multi-threaded programming and more specifically to a method of providing thread-safe access to data having a hierarchical structure.
A computer program is a sequence of instructions that can be executed by a computer. Instructions within computer programs can be organized into threads for the purposes of separating functionality. A thread is a process that is part of a larger process or program. Threads may be executed concurrently or in a round-robin scheduling scheme. Threads generally provide a technique for organizing code in computer programs, allowing improved performance and responsiveness to external interfaces.
Data accessed by computer program threads can be organized in a hierarchical fashion. These hierarchies can store data, represented by objects, such that data retrieval and maintenance operations are improved. Web content, including text and graphics, is often organized in hierarchies. Languages exist to define these hierarchies. For example, eXtensible Markup Language (xe2x80x9cXMLxe2x80x9d) is a specification for designing formats for text data that allows for text objects to be organized into hierarchies (i.e., XML documents). XML lets Web developers and designers create customized tags that offer flexibility in organizing and presenting information.
A common way to build object-based systems for use with multiple threads is to associate a lock with each object. Operations that might be performed incorrectly if multiple threads were simultaneously accessing an object are defined as synchronized, that is, the operation will interact with a locking mechanism to insure the proper order of execution. Whenever a synchronized operation is performed on an object, the object""s lock is first obtained, preventing any other thread from performing any synchronized operation on the object until the completion of the operation holding the lock. While this method of synchronization is useful for many purposes, it frequently is not suitable for an interconnected set of objects in a hierarchical structure. Problems may arise because an operation on an object frequently cannot be completed without performing operations on its parent or child objects. In a graphical user interface (GUI), for example, a slider control object may be defined as a child of the parent dialog object. Now, consider what happens if a thread A performs an operation on the slider object at about the same time as another thread B performs an operation on the dialog object. Thread A will lock the slider object and thread B will lock the dialog object, but if thread A""s operation cannot be completed without first locking all its ancestor objects and thread B""s operation cannot be completed without first locking all its descendant objects a classic xe2x80x9cdeadlockxe2x80x9d situation will occur and result in both threads becoming blocked forever, causing portions of the graphical user interface to become inoperative.
A simpler way to support operations on objects in a hierarchy is to allow just one thread at a time to perform operations on objects in the hierarchy. Depending on the nature of the system, such an architecture still offers some scope for multithreading if there are multiple hierarchies or there is a mechanism for transferring control of a specific hierarchy from one thread to another. With multiple hierarchies (e.g., several windows being displayed on the screen, and the objects displayed in each window being contained in a separate hierarchy associated with each window), each hierarchy can be under the control of a different thread. Multithreading can also be provided by using a mechanism for transferring control of a hierarchy from one thread to another. With a transferring mechanism, before a thread A could perform an operation on an object, thread A would first have to gain control of the hierarchy containing the object. If some other thread B controls the hierarchy, thread A would have to wait for thread B to finish its current operation in the hierarchy and relinquish control of it. Implementing either of these cases will provide limited multithreading. An alternative mechanism, representing the simplest possible system, provides that a given thread is the only thread that ever performs any operation on any object in the hierarchy. This approach can prevent locking problems, but only provides multithreading when independent hierarchies are controlled by different threads. In all these cases, deadlock is avoided because at any point in time there is at most one thread that is in the process of performing any operation on any object in a given hierarchy. Thus, no matter what objects in the hierarchy need to be accessed in order to perform an operation, it is guaranteed that no other thread is currently accessing any of those objects.
An operation within a hierarchy often involves accessing multiple objects. Problems arise when using threaded programming techniques if an operation on an object cannot be completed without performing operations on its parent or child objects. Therefore, these existing methods of providing thread-safe access in a mult-threaded environment are less than adequate or ideal.
In a single-threaded environment the appearance of concurrent access to multiple objects can be achieved by emulating multi-threading using a polling technique. The single thread can thus respond to multiple requests and emulate concurrent access, but such programming is error-prone and often cannot use standard library functions because they are not written to include the requisite polling operations.
Multi-threaded solutions often involve locks to insure proper access to multiple objects. One multi-threading technique involves creating a lock per object. It is extremely difficult to design all operations that can be performed on objects in a way that is free from deadlock when a lock-per-object synchronization strategy is used. In addition, the cost of just obtaining and releasing locks for all of the objects involved in an operation can be very substantial, in many cases dominating all other costs of performing the operation. Alternate multi-threading techniques include: 1) using a separate thread for each separate hierarchy, 2) using one thread that is switched between each separate hierarchy and 3) using a separate, hard-coded, thread for each separate hierarchy.
There are some operations that are not handled very satisfactorily by any of the techniques discussed above. Therefore, a general mechanism allowing multiple threads of control to work together within an application that uses hierarchies is preferable. In these situations, it is often highly desirable to have different threads operating simultaneously in different parts of a hierarchy. One example of such a situation is where a graphical window is defined with several panes, each of which is showing an independently controlled animated sequence of images. Another example is a Web browser application where it is desirable to assign to one thread the responsibility for controlling the content displayed in the browser window, while a different thread controls the menus, buttons, and other user-interface elements that are used to control the browser application. In these cases, it is desirable to have the user-interface elements that control the application remain responsive, even while the content to be displayed is being computed or downloaded.
Accordingly, it would be desirable to provide methods and apparatus for ensuring thread-safe access to a hierarchy of objects. The present invention provides a mechanism allowing different threads the ability to operate simultaneously in different parts of a hierarchy. This satisfies the requirements of speed and safety, without returning to the deadlock-prone model in which every object has its own lock. The present invention utilizes a mechanism for partitioning a hierarchy into subhierarchies, each of which can be controlled by a different thread. Using this mechanism, such subhierarchies have thread interface frames at their roots. A thread interface frame provides a way to partition a hierarchy and provide efficient operations on the hierarchy. A thread interface frame can be a program interface that can include a set of methods, procedures and/or functions. The descendant objects of a thread interface frame can be manipulated by a different thread from the thread that manipulates the ancestor objects of the thread interface frame. In order to provide this type of access safely, the thread interface frames have special implementations of operations that require accessing objects on opposite sides of the thread interface frame within the hierarchy. The implementations of these operations in the thread interface frames can use techniques that are more expensive (in time, space, or both) than the standard implementations of these operations that are used on all other objects, but the overall impact on system performance is mitigated by the fact that the extra time and space costs are only incurred when the thread interface frame is used, rather than being incurred on operations at every object. It is expected that thread interface frames will be used only in those situations where it is important to enable more than one thread to perform operations simultaneously within the same hierarchy.
An embodiment of the present invention provides a method of operating on objects in a hierarchy by partitioning the hierarchy into subhierarchies, each subhierarchy containing objects and being associated with a thread interface frame. Operations of the thread interface frame are then executed within threads acting on objects in the subhierarchy. When needed, the effects of an operation are stored in the thread interface frame, allowing the effects to be forwarded to another subhierarchy accessed by another thread.
One effect of an operation can be to control access to objects in the subhierarchy, allowing just one thread, at any given time, access to the objects in the subhierarchy. The access can be controlled by a lock object associated with the thread frame interface.
One such operation arises in the processing of nonlocal options. Objects of a class may contain fields. Options are a mechanism for a class that work like fields but offer a different space/time tradeoff. Options can hold values and optionally have default value settings. Options can be local or nonlocal. Local options affect only the object upon which they are defined. Nonlocal options provide a mechanism by which the setting of an option value on one object can influence the value that is read using the same option name on another object. In one embodiment of the present invention, the effect of the operation comprises setting the nonlocal option value, influencing the option value that is read using the same option name on another object in the hierarchy. The thread interface frame can maintain a copy of the nonlocal option value, such that the operation of reading the value will not require access to the parent of the thread interface frame in the hierarchy to retrieve the nonlocal option value.
In another embodiment of the present invention, the effect of the operation is to propagate a nonlocal option value change notification through the thread interface frame to objects in the hierarchy. In further embodiments of the present invention, the effect of the operation comprises: getting the nonlocal option value, including accessing ancestor objects of the subhierarchy; and registering for change notification events on the nonlocal option.
In yet another embodiment of the present invention, the hierarchy of objects contains graphical objects. The graphical objects can be used to represent the components of a graphical user interface. In such an embodiment, the effect of the operation may further comprise: repainting a screen region represented by the hierarchy; renegotiating a layout for a screen region represented by the hierarchy; and obtaining width and/or height preferences for a screen region represented by the hierarchy.